package 面试经典150题.二分查找;

/**
 * @author tmh
 * @date 2024/6/10 22:30
 * @description 这个二分法的mid有点神奇，好久还要系统的在巩固学习下
 */
public class T74搜索二维矩阵 {
    public static void main(String[] args) {
        int[][] mat ={{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        searchMatrix(mat,38);
    }
        public static boolean searchMatrix(int[][] mat, int t) {
            int m = mat.length, n = mat[0].length;

            // 第一次二分：定位到所在行（从上往下，找到最后一个满足 mat[x]][0] <= t 的行号）
            int l = 0, r = m - 1;
            while (l < r) {
                //mid = l + r + 1 >> 1;这里如果不加1的话就会死循环，其他的思路就是一样的，如果mid小于等于目标值，left=mid
                int mid = l + r + 1 >> 1;
                if (mat[mid][0] <= t) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }

            int row = r;
            if (mat[row][0] == t) {
                return true;
            }
            if (mat[row][0] > t) {
                return false;
            }

            // 第二次二分：从所在行中定位到列（从左到右，找到最后一个满足 mat[row][x] <= t 的列号）
            l = 0;
            r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (mat[row][mid] <= t) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            int col = r;

            return mat[row][col] == t;
        }
    }
